#include <bitset>
#include <iostream>

using ull = unsigned long long;

ull n, m, c, k, input, _;
const ull max_k = 64+5;
// const ull max_n = 1e6+5;
ull used_bits;
std::bitset<max_k> vis_bits;

#define NV(v)#v<<" : "<<(v)

#ifdef ONLINE_JUDGE
    #define DEBUG(code)
#else
    #define DEBUG(code)code
#endif

int main(){
    
    
    std::iostream::sync_with_stdio(false), std::cin.tie(nullptr), std::cout.tie(nullptr);

    std::cin>>n>>m>>c>>k;

    if(n==0 && m==0 && k==64){
        std::cout<<"18446744073709551616\n";
        return 0;
    }

    for(ull i{1};i<=n;i++){
        std::cin>>input;
        DEBUG(std::cout<<NV(input)<<" ";)
        DEBUG(std::cout<<NV(std::bitset<4>(input))<<" ";)
        used_bits |= input;
        DEBUG(std::cout<<'\n';)
    }
    for(ull i{1};i<=m;i++){
        std::cin>>input>>_;
        if(!((used_bits>>input)&1) && vis_bits[input]==false){
            DEBUG(std::cout<<"unused_bit++ ;"<<NV(input)<<'\n';)
            k--;
            vis_bits[input] = true;
        }
    }
    const auto left_shift = [](const ull n, const ull num)->ull{
        return num < 64 ? n<<num : 0;
    };
    DEBUG(std::cout<<NV(k)<<'\n';)
    std::cout<<(left_shift(1, k)) - n<<'\n';
}